1. Field of the Invention
The present invention is related to a graphic related data processing, more particularly to an apparatus and a method of processing graphic data using index based triangle listing.
2. Related Art
With the fast growing popularity of social network applications in our society, social network analysis has emerged as a key technology that provides better social networking services. This is achieved through automated discovery of relationships within the social network and using this insight to provide value-added services, such as friend discovery, personalized advertisements, and spam filtering to name a few.
Social networks are used to capture and represent the relationships between members of social systems at all scales, from interpersonal to international. Using graphs is a typical methodology to represent social networks, where nodes of the graph connote people and edges connote their relationships, such as short messages, mobile calls, and email exchanges.
Triangle listing is a basic operator in dealing with many graph data such as social networks. However, in-memory algorithms don't work well in recent massive graphs since these graphs are so massive that they cannot fit into the memory. Although new algorithms based on external memory have been introduced, the existing studies still suffer from frequent multiple scans of the whole graph on the disk and tremendous calculation coming from involving the whole graph in every iteration.
Therefore, an I/O-efficient processing apparatus and method for massive graph based on triangle listing is needed.